/**
 * @file DoubleLinkedList.h
 * @author ikun (2732608951@QQ.com)
 * @brief  Implementation of the class of a double linked list
 * @version 0.1
 * @date 2022-10-04
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#ifndef DOUBLELINKEDLIST_H_
#define DOUBLELINKEDLIST_H_

#include<iostream>
#include<cstdlib>
using namespace std;
/**
 * @brief define a class of a double linked class 
 * The class includes a structure named Node,
 * two nested class named const_iterator and
 * iterator for visitation of objects,two Node* 
 * pointers named head and tail and Big Five functions.  
 */
template <typename DT>
class DoubleLinkedList
{
    private:
        /**
         * @brief A brief discprition of Node
         * 
         */
        struct Node
        {
            DT data;///< type of data is undefined                             
            Node *prev;///< point to the previous node                      
            Node *next;///< point to the next node
            /**
             * @brief Construct a new Node object when 
             * an lvalue is transmitted in
             * 
             * @param d
             * @param p 
             * @param n 
             */
            Node(const DT& d=DT{},Node* p=nullptr,Node* n=nullptr)
            :data{d},prev{p},next{n}{}
            /**
             * @brief Construct a new Node object when an lvalue is transmitted
             * 
             *
             * @param d An rvalue reference type and for initialization, the properity
             * of which is changed into lvalue when the function move calls
             * @param p For initialization
             * @param n For initialization
             */
            Node(DT &&d,Node* p=nullptr,Node* n=nullptr)
            :data{std::move(d)},prev{p},next{n}{}
        };
        /**
         * @brief A brief discprition of const_iterator
         * The const_iterator is unable to change member
         * variables, but can visit objects of constant 
         * type
         */
    public:
        class const_iterator
        {

        public:
        /**
         * @brief Construct a new const iterator object
         * 
         */
            const_iterator() : current(nullptr){}
        /**
         * @brief Redefine the operator *,
         * using for read the data of the node
         * 
         * @return const DT& 
         */
            const DT& operator*()const
            {
                return retrieve();
            }
        /**
         * @brief Redefine the operator ++(front type).
         * current point to the next node
         * 
         * @return const_iterator& 
         */
            const_iterator& operator++()
            {
                current=current->next;
                return *this;
            }
        /**
         * @brief Redefine the operator ++(back type)
         * Due to old is temporary, usage of reference is wrong
         * 
         * @return const_iterator 
         */

            const_iterator & operator++(int)
            {
                const_iterator old=*this;
                ++(*this);
                return old;
            }
            /**
             * @brief visit the previous node
             * 
             * @return const_iterator& 
             */
            const_iterator & operator--()
            {
                current=current->prev;
                return *this;
            }
            /**
             * @brief visit the previous node
             * 
             * @return const_iterator 
             */

            const_iterator operator--(int)
            {
                const_iterator old=*this;
                --(*this);
                return old;

            }
            /**
             * @brief Redefine ==
             * Judje whether two iterators are identical
             * 
             * @param rhs Transmit the pointer of the node into
             * @return true 
             * @return false 
             */

            bool operator==(const const_iterator & rhs)const
            {
                return current==rhs.current;
            }
            /**
             * @brief akin to the overload ==
             * 
             * @param rhs 
             * @return true 
             * @return false 
             */
            bool operator!=(const const_iterator & rhs)const
            {
                return !(*this==rhs);
            }

        protected:
            /**
             * @brief Copy the pointer of node in existence
             * It's procted thus it could be visited by the inheritance
             * of the class
             */
            Node *current;   

            /**
             * @brief Return the reference of data pointed by current
             * 
             * @return DT& 
             */
            DT& retrieve()const
            {
                return current->data;
            }

            /**
             * @brief Construct a new const iterator object
             * 
             * @param p 
             */
            const_iterator(Node* p): current{p}{}
            /**
             * @brief able to visit any member in DoubleLInkedList
             * 
             */
            friend class DoubleLinkedList<DT>;

        };

        /**
         * @brief the public type inheritance of const_iterator
         * It could only visit auto objects and all the member functions
         * below are akin to its parent class, so they won't be introduced
         * in detail
         */
        class iterator:public const_iterator
        {
            public:
                iterator(){}

                DT& operator*()
                {
                    return const_iterator::retrieve();
                }
                const DT& operator*()const
                {
                    return const_iterator:: operator*();
                }

                iterator& operator++()
                {
                    this->current=this->current->next;
                    return *this;
                }

                iterator  operator++(int)        
                {
                    iterator old = *this;
                    ++(*this);
                    return old;
                }

                iterator operator--()
                {
                    this->current=this->current->prev;
                    return *this;
                }

                iterator operator--(int)
                {
                    iterator old = *this;
                    --(*this);
                    return old; 
                }
            
            protected:
            /**
             * @brief Construct a new iterator object
             * the constructor of its parent fuction is called
             * 
             * @param p 
             */
                iterator(Node* p):const_iterator{p}{};

                friend class DoubleLinkedList<DT>;
        };

    public:
    /**
     * @brief Construct a new Double Linked List object
     * 
     */
        DoubleLinkedList(){init();}

    /**
     * @brief Destroy the Double Linked List object
     * 
     */
        ~DoubleLinkedList()
        {
            clear();
            delete head;
            delete tail;
        }

        /**
         * @brief Construct a new Double Linked List object
         * Copy constructor. Local variable x was used for
         * traversing the container.
         * 
         * @param rhs the object used for copy
         */
        DoubleLinkedList(const DoubleLinkedList& rhs)
        {
            init();
            for(auto & x:rhs)
                push_back(x);
        }

        /**
         * @brief assignment operation
         * It is called when an lvalue is transmitted
         * 
         * @param rhs 
         * @return DoubleLinkedList& 
         */
        DoubleLinkedList& operator=(const DoubleLinkedList& rhs)
        {
            DoubleLinkedList copy=rhs;
            std::swap(*this, copy);
            return *this;
        }

        /**
         * @brief Construct a new Double Linked List object
         * It's a move constructor, avoiding the copying process
         * 
         * @param rhs 
         */
        DoubleLinkedList(DoubleLinkedList && rhs)
        :theSize{rhs.theSize},head{rhs.head},tail{rhs.tail}
        {
            rhs.theSize=0;
            rhs.head=nullptr;
            rhs.tail=nullptr;
        }

        /**
         * @brief It's a move assignment
         * It was used to avoid the process of copy
         * 
         * @param rhs 
         * @return DoubleLinkedList& 
         */
        DoubleLinkedList& operator=(DoubleLinkedList && rhs)
        {
            std::swap(theSize,rhs.theSize);
            std::swap(head,rhs.head);
            std::swap(tail,rhs.tail);
            return *this;
        }

        /**
         * @brief return the first node
         * 
         * @return iterator 
         */
        iterator begin()
        {return {head->next};}
        
        /**
         * @brief return the first node, called by a constant object
         * 
         * @return const_iterator 
         */
        const_iterator begin() const
        {return {head->next};}

        /**
         * @brief return tail
         * 
         * @return iterator 
         */
        iterator end()
        {return {tail};}

        /**
         * @brief return tail, able to visit constant object
         * 
         * @return const_iterator 
         */
        const_iterator end() const
        {return {tail};}
        
        /**
         * @brief return the number of Node structures
         * 
         * @return int 
         */
        int size()const
        {return theSize;}

        /**
         * @brief judje if the class dosen't have any node
         * 
         * @return true 
         * @return false 
         */
        bool empty()const
        {return size()==0;}

        /**
         * @brief delete all nodes
         * 
         */
        void clear()
        {
            while(!empty())
                pop_front();
        }

        /**
         * @brief Return the data of the first node
         * '*' was overloaded
         * 
         * @return DT& 
         */
        DT& front()
        {return *begin();}

        /**
         * @brief const type
         * 
         * @return const DT& 
         */
        const DT& front()const
        {return *begin();}

        /**
         * @brief return the data of the last node
         * 
         * @return const DT& 
         */
        const DT& back()const
        {return *--end();}

        /**
         * @brief Insert the element as first node
         * Called when lvalue was transmitted
         * 
         * @param x 
         */
        void push_front(const DT& x) 
        {insert(begin(),x);}

        /**
         * @brief akin to above but called when an rvalue was transmitted
         * 
         * @param x 
         */
        void push_front(DT && x)
        {insert(begin(),std::move(x));}

        /**
         * @brief Similar to above
         * 
         * @param x 
         */
        void push_back(const DT& x)
        {insert(end(),x);}

        /**
         * @brief Similar to above
         * 
         * @param x 
         */
        void push_back(const DT && x)
        {insert(end(),std::move(x));}

        void pop_front()
        {erase(begin());}                  

        void pop_back()
        {erase(--end());}

        /**
         * @brief Construct a node and insert before the itr pointer
         * 
         * @param itr 
         * @param x 
         * @return iterator 
         */
        iterator insert(iterator itr,const DT& x)
        {
            Node *p=itr.current;
            theSize++;
            return {p->prev=p->prev->next=new Node{x,p->prev,p}};
        }

        /**
         * @brief similar to above but avoid copy
         * 
         * @param itr 
         * @param x 
         * @return iterator 
         */
        iterator insert(iterator itr,DT && x)
        {
            Node *p = itr.current;
            theSize++;
            return{p->prev=p->prev->next=new Node{x,p->prev,p}};
        }

        /**
         * @brief Delete the node pointed by itr
         * Return the next pointer after itr
         * @param itr 
         * @return iterator 
         */
        iterator erase(iterator itr)
        {
            Node *p=itr.current;
            iterator retVal{p->next};
            p->prev->next=p->next;
            p->next->prev=p->prev;
            delete p;
            theSize--;
            return retVal;
        }
        /**
         * @brief earase from pointer from until to and return to
         * 
         * @param from 
         * @param to 
         * @return iterator 
         */
        iterator erase(iterator from,iterator to)
        {
            for(iterator itr=from;itr!=to;)
                itr=erase(itr);
            return to;
        }

        /**
         * @brief print the all the data in the container
         * 
         */
        void printList()
        {
            for(Node *p=head->next;p!=tail;p=p->next)
            {
                cout << p->data<< " ";
            }
            cout << '\n';
        }
        iterator find(DoubleLinkedList<DT>& _list,const DT& _val);
    private:
        int theSize;         ///<number of nodes
        Node *head;          ///<the pointer before first node
        Node *tail;          ///<the pointer after last node

        /**
         * @brief used for constructor
         * 
         */
        void init()     
        {
            theSize=0;
            tail=new Node;
            head=new Node;
            head->next=tail;
            tail->prev=head;
        }



        

};



#endif